class Solution {
public:
    void nextSort(vector<int>& vecArr){

        int pos=vecArr.size()-2;
        while(pos>=0 && vecArr[pos]>=vecArr[pos+1]){
            --pos;
        }
        if(pos<0){
            reverse(vecArr.begin(),vecArr.end());
        }
        else{
            int j=vecArr.size()-1;
            while(vecArr[j]<=vecArr[pos]){
                --j;
            }
            swap(vecArr[pos],vecArr[j]);
            reverse(vecArr.begin()+pos+1,vecArr.end());
        }
    }
    string getPermutation(int n, int k) {
        
        vector<int> vecArr(n);
        int t=1;
        for(int i=0;i<n;++i){
            vecArr[i]=i+1;
            t*=i+1;
        }
        k-=1;
        k%=t;
        while(k--){
            nextSort(vecArr);
        }
    
        string sRet;
        for(int i=0;i<vecArr.size();++i){
            sRet+=vecArr[i]+'0';
        } 

        return sRet;
    }
};
